package leetcode_day._2021._202112._0110;

import java.util.Arrays;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/3 21:51
 * K 次取反后最大化的数组和
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 * 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 * 以这种方式修改数组后，返回数组 可能的最大和 。
 * 算法：贪心
 */
public class _03_1005 {
    public static void main(String[] args) {
        largestSumAfterKNegations(new int[]{2,-3,-1,5,-4}, 2);
    }

    public static int largestSumAfterKNegations(int[] nums, int k) {
        int len = nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) if (nums[i] < 0 && --k >= 0) nums[i] *= -1;
        if (k > 0 && k % 2 != 0) {
            int idx = 0;
            for (int i = 0; i < len; i++) idx = nums[idx] > nums[i] ? i : idx;
            nums[idx] *= -1;
        }
        int ans = 0;
        for (int i = 0; i < len; i++) ans += nums[i];
        return ans;

    }

}
